package function;

import dto.Node;

/**
 * @Description TODO
 * @Author li
 * @Date 2022/2/28 7:24 上午
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class CopyRandomList {

    public static void main(String[] args) {
        Node head = new Node(7);
        Node node = new Node(13);
        node.random = new Node(0);
        head.next = node;
        Node node1 = new Node(11);
        node1.random = new Node(4);
        head.next.next = node1;
        Node node2 = new Node(10);
        node2.random = new Node(2);
        head.next.next.next = node2;
        Node node3 = new Node(1);
        node3.random = new Node(0);
        head.next.next.next.next = node3;
        copyRandomList(head);
    }

    public static Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        Node cur = head;
        while(cur != null){
            int val = cur.val;
            // 组装一个新的node
            Node copyNode = new Node(val);
            copyNode.next = cur.next;
            // 将组织新的node 替换掉原来的next
            cur.next = copyNode;
            // 在还原原来的  但是head已经改变了
            cur = cur.next.next;
        }

        cur = head;
        while(cur != null){
            if(cur.random != null){
                cur.next.random = cur.random;
            }
            // 跳过重复那个
            cur = cur.next.next;

        }
        // 13，13.。。
        Node copyHead = head.next;
        // 7,7,13,13,11
        cur = head;
        // 13，13.。。
        Node curCopy = head.next;
        while(cur != null){
            // 13,13,11,11
            Node next = cur.next.next;
            // 7，13,13,11，11
            cur.next = next;
            // 13,13,11,11
            Node next1 = cur.next;
            // 13,13,11,11
            cur = next1;

            if(curCopy.next != null){
                // 13，11,11,...
                Node next2 = curCopy.next.next;
                // 7,13,11,11
                curCopy.next = next2;
                // 13,11,11
                Node next3 = curCopy.next;

                curCopy = next3;
            }
        }
        return copyHead;
    }
}
